/**
 * 循环双向链表
 * 头结点的前驱指针域指向最后一个节点, 最后一个节点的后继指针域指向头结点
 */
#include <stdlib.h>
#include "./DoubleCircleLinkedList.h"

// 初始化链表
Status InitList(DoubleCircleLinkedList *list) {
    Node *tmp = (Node*)malloc(sizeof(Node));
    if(!tmp) {
        return ERROR;
    }
    *list = tmp;
    // 循环双向链表这里有区别于 双向链表, 就是头结点的前驱指针域指向最后一个节点, 最后一个节点的后继指针域指向头结点
    (*list)->prev = *list;
    (*list)->next = *list;
    return OK;
}

// 链表是否为空
int ListIsEmpty(DoubleCircleLinkedList list) {
    return list->prev == list->next == list;
}

// 销毁链表
Status DestroyList(DoubleCircleLinkedList *list) {
    // 当前结点, 首次为头结点
    // 因为是 双向链表, 则可以从 尾结点 顺着 前驱 向上找(待销毁)
    Node *curNode = (*list);
    // 记录下头结点, 要比较
    Node *headNode = (*list)->next;
    // 结束条件, 当前节点是头节点
    while(curNode != headNode) {
        // 当前结点 销毁后的新链表
        *list = curNode->prev;
        // 新链表的 后驱指针域 指向头节点
        (*list)->next = curNode->next;
        // 头结点的 前驱指针域 指向最后一个结点
        curNode->next->prev = (*list);
        // 销毁当前结点
        free(curNode);
        // 销毁当前结点后, 将当前结点指针向前移动
        curNode = *list;
    }
    // 最后只剩下 头结点了, 然后将头结点销毁
    free(curNode);
    *list = NULL;
    return OK;
}

// 获取链表长度
unsigned int ListLength(DoubleCircleLinkedList list) {
    Node *curNode = list;
    unsigned int len = 0;
    // 当前结点不为 头结点时, 则为数据元素 参加计算
    while(curNode != list->next) {
        len++;
    }
    return len;
}

// 获取指定位置的元素,  index可取范围是 1 - 链表的长度
Status GetElem(DoubleCircleLinkedList list, int index, ElemType *e) {
    if(index < 1) {
        return 0;
    }
    // 当前结点, list为尾指针, 第一次为 首元结点
    Node *curNode = list->next->next;
    int curIdx = 1;
    while(curIdx < index && curNode != list->next) {
        curNode = curNode->next;
        curIdx++;
    }
    if(curNode == list->next) {
        return ERROR;
    }
    *e = curNode->data;
    return OK;
}

// 在指定位置插入元素
Status InsertElem(DoubleCircleLinkedList *list, int index, ElemType e) {
    if(index < 1) {
        return ERROR;
    }
    // 从头结点开始查找, list是尾指针, list的指针域指向头结点
    Node *curNode = (*list)->next;
    int curIdx = 0;
    while(curIdx < index-1 && curNode != (*list)) {
        curNode = curNode->next;
        curIdx++;
    }
    if(curNode == (*list) && curIdx < index-1) {
        return ERROR;
    }
    Node *tmp = (Node*)malloc(sizeof(Node));
    if(!tmp) {
        return ERROR;
    }

    tmp->data = e;
    // curNode是index-1 位置的结点
    // index-1位置的结点 的 后继结点的 前驱指针域 指向新结点
    curNode->next->prev = tmp;
    // 新节点的后继指针域 指向 index-1位置的结点的 后继结点
    tmp->next = curNode->next;
    // index-1 位置的后继指针域指向新结点
    curNode->next = tmp;
    // 新节点的前驱指针域 指向 index-1位置的结点
    tmp->prev = curNode;

    // 判断, 如果是在链表的结尾插入的元素, 则需要 向后移动尾指针
    if(curIdx == index-1 && curNode == *list) {
        *list = tmp;
    }
    return OK;
}

Status DeleteElem(DoubleCircleLinkedList *list, int index, ElemType *e) {
    if(index < 1) {
        return ERROR;
    }
    // 指向首元结点
    Node *curNode = (*list)->next->next;
    int curIdx = 1;
    while(curNode != (*list) && curIdx < index) {
        curNode = curNode->next;
        curIdx++;
    }
    // 到最后, 还是没找到我想要的位置, 说明位置超过了链表的长度
    if(curNode == (*list) && curIdx < index) {
        return ERROR;
    }

    // 如果删除的是最后一个结点, 则需要向前移动 尾指针
    if(curNode == (*list) && curIdx == index) {
        *list = curNode->prev;
    }
    curNode->prev->next = curNode->next;
    curNode->next->prev = curNode->prev;
    free(curNode);
    return OK;
}

int main() {
    DoubleCircleLinkedList list;
    InitList(&list);
    return 0;
}